﻿/**
 * List
 *
 * @author		Allen Chou
 * @version		1.0.1 (last update: Jan 17 2009)
 * @link        http://cjcat.blogspot.com
 * @link		http://cjcat2266.deviantart.com
 */

package idv.cjcat.ds {

	/**
	 * The <code>List</code> class represnts the doubly liked list data structure.
	 */
	public class List implements ICollection {
		
		/** @private */
		internal var _head:ListNode;
		/** @private */
		internal var _tail:ListNode;
		
		private var _size:int;
		private var _tempNode:ListNode;
		
		/**
		 * Creates a list.
		 * @param	...items  The items to be contained in the list.
		 */
		public function List(...items) {
			_head = _tail = null;
			_size = 0;
			
			for each (var obj:* in items) push(obj);
		}
		
		/**
		 * @inheritDoc
		 */
		public function contains(item:*):Boolean {
			//empty
			if (_head == null) return false;
			_tempNode = _head;
			
			do {
				if (_tempNode.data == item) return true;
				_tempNode = _tempNode.next;
			} while (_tempNode != null);
			return false;
		}
		
		/**
		 * @inheritDoc
		 */
		public function clear():void {
			_head = _tail = null;
			_size = 0;
		}
		
		/**
		 * @inheritDoc
		 */
		public function isEmpty():Boolean {
			return _head == null;
		}
		
		/**
		 * Adds an item at the end of the list.
		 * @param	item  The item.
		 */
		public function push(item:*):void {
			_size++;
			
			//empty
			if (_head == null) {
				_head = _tail = new ListNode(item);
				return;
			}
			
			//one item only
			if (_head == _tail) {
				_tail = new ListNode(item);
				_tail.prev = _head;
				_head.next = _tail;
				return;
			}
			
			//more than one item
			_tempNode = _tail;
			_tail = new ListNode(item);
			_tail.prev = _tempNode;
			_tempNode.next = _tail;
		}
		
		/**
		 * Adds an item at the beginning of the list.
		 * @param	item  The item.
		 */
		public function unshift(item:*):void {
			_size++;
			
			//empty
			if (_tail == null) {
				_head = _tail = new ListNode(item);
				return;
			}
			
			//one item only
			if (_head == _tail) {
				_head = new ListNode(item);
				_head.next = _tail;
				_tail.prev = _head;
				return;
			}
			
			//more than one item
			_tempNode = _head;
			_head = new ListNode(item);
			_head.next = _tempNode;
			_tempNode.prev = _head;
		}
		
		/**
		 * Removes the last item of the list.
		 * @return  The removed item.
		 */
		public function pop():* {
			_size--;
			
			_tempNode = _tail;
			_tail = _tail.prev;
			_tail.next = null;
			
			return _tempNode.data;
		}
		
		/**
		 * Removes the first node of the list.
		 * @return  The data carried by the removed node.
		 */
		public function shift():* {
			_size--;
			
			_tempNode = _head;
			_head = _head.next;
			_head.prev = null;
			
			return _tempNode.data;
		}
		
		/**
		 * Adds multiple items at the end of the list.
		 * @param	...items  The items.
		 */
		public function append(...items):void {
			for (var i:int = 0; i < items.length; i++) push(items[i]);
		}
		
		/**
		 * Adds multiple items at the head of the list.
		 * @param	...items  The items.
		 */
		public function prepend(...items):void {
			for (var i:int = items.length - 1; i >= 0; i--) unshift(items[i]);
		}
		
		/**
		 * Appends a list at the tail of the current list.
		 * @param	list  The list to be appended.
		 */
		public function postJoin(list:List):void {
			this._tail.next = list._head;
			list._head.prev = this._tail;
			list._head = this._head;
			this._tail = list._tail;
			
			this._size = list._size = this._size + list._size;
		}
		
		/**
		 * Prepends a list a the head of the current list.
		 * @param	list  The list to be prepended.
		 */
		public function preJoin(list:List):void {
			list.postJoin(this);
		}
		
		/**
		 * Splices a list in to the current list.
		 * <p>
		 * The iterator must point to nodes other than the head.
		 * To prepend a list to the current list, use the <code>prepend()</code> method instead.
		 * To remove nodes from the head of the list, use the <code>pop()</code> method instead.
		 * </p>
		 * @param	iterator     The position where a list is spliced into. After the splicing, the node pointed by the iterator is appended after the spliced list.
		 * @param	deleteCount  The number of nodes removed after the iterator position.
		 * @param	list         The list to be spliced into the current list.
		 * @return  A list of removed nodes.
		 */
		public function splice(iterator:ListIterator, deleteCount:uint = 0, list:List = null):List {
			var originalIterator:ListIterator = iterator;
			iterator = iterator.clone();
			var actualDeleteCount:int = 0;
			var returnList:List = new List();
			var initNode:ListNode = iterator._node;
			
			for (var i:int = 0; i < deleteCount; i++) {
				actualDeleteCount++;
				if (iterator.hasNext()) {
					iterator.next();
				} else {
					iterator.next();
					break;
				}
			}
			
			if (actualDeleteCount > 0) {
				var emptySplice:Boolean = false;
				if (list == null) {
					emptySplice = true;
				} else if (list._size == 0) {
					emptySplice = true;
				}
				
				if (iterator._node != null) {
					_tempNode = iterator._node.prev;
					if (emptySplice) {
						_tempNode.next = null;
						initNode.prev.next = iterator._node;
						
						iterator._node.prev = initNode.prev;
						initNode.prev = null;
					} else {
						initNode.prev.next = list._head;
						list._head.prev = initNode.prev;
						list._head = this._head;
						initNode.prev = null;
						
						iterator._node.prev = list._tail;
						list._tail.next = iterator._node;
						list._tail = this._tail;
						_tempNode.next = null;
					}
					returnList._head = initNode;
					returnList._tail = _tempNode;
				} else {
					//tail reached
					returnList._head = initNode;
					returnList._tail = this._tail;
					
					initNode.prev.next = list._head;
					list._head.prev = initNode.prev;
					initNode.prev = null;
					list._head = this._head;
					this._tail = list._tail;
				}
				
				returnList._size = actualDeleteCount;
			} else {
				//no node removal
				if (!emptySplice) {
					_tempNode = initNode.prev;
					
					_tempNode.next = list._head;
					list._head.prev = _tempNode;
					list._head = this._head;
					
					initNode.prev = list._tail;
					list._tail.next = initNode;
					list._tail = this._tail;
				}
			}
			
			this._size = list._size = this._size + list._size - actualDeleteCount;
			originalIterator._list = returnList;
			
			return returnList;
		}
		
		public function spliceItems(iterator:ListIterator, deleteCount:uint = 0, ...items):List {
			var tempList:List = new List();
			for each (var item:* in items) tempList.push(item);
			return splice(iterator, deleteCount, tempList);
		}
		
		/**
		 * @inheritDoc
		 */
		public function getIterator():Iterator {
			return new ListIterator(_head, this);
		}
		
		/**
		 * The first node of the list.
		 */
		public function get head():ListNode { return _head; }
		/**
		 * The last node of the list.
		 */
		public function get tail():ListNode { return _tail; }
		/**
		 * @inheritDoc
		 */
		public function get size():int { return _size; }
		
		/**
		 * Returns a string representation of the list.
		 */
		public function toString():String {
			if (_head == null) return "";
			
			var str:String = "";
			_tempNode = _head;
			while (true) {
				str += _tempNode.data.toString();
				_tempNode = _tempNode.next;
				if (_tempNode != null) {
					str += ", ";
				} else {
					break;
				}
			}
			return str;
		}
		
	}
}